﻿//给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
//当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
//请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
//注意：不允许旋转信封。
//
//输入：envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]
//输出：3
//解释：最多信封的个数为 3, 组合为: [2, 3] = > [5, 4] = > [6, 7]。
//
//输入：envelopes = [[1, 1], [1, 1], [1, 1]]
//输出：1
//
//提示：
//	1 <= envelopes.length <= 10^5
//	envelopes[i].length == 2
//	1 <= wi, hi <= 10^5

// class Solution {
// public:
//     int maxEnvelopes(vector<vector<int>>& e) {
//         // 解法⼀：动态规划

//         // 预处理

//         sort(e.begin(), e.end());
//         int n = e.size();
//         vector<int> dp(n, 1);
//         int ret = 1;
//         for (int i = 1; i < n; i++) {
//             for (int j = 0; j < i; j++) {
//                 if (e[i][0] > e[j][0] && e[i][1] > e[j][1]) {
//                     dp[i] = max(dp[i], dp[j] + 1);
//                 }
//             }
//             ret = max(ret, dp[i]);
//         }
//         return ret;
//     }
// };

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& e) {
        // 解法⼆：重写排序+贪⼼+⼆分

        sort(e.begin(), e.end(),
            [&](const vector<int>& v1, const vector<int>& v2) {
                return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
            });
        // 贪⼼+⼆分

        vector<int> ret;
        ret.push_back(e[0][1]);
        for (int i = 1; i < e.size(); i++) {
            int b = e[i][1];
            if (b > ret.back()) {
                ret.push_back(b);
            }
            else {
                int left = 0, right = ret.size() - 1;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (ret[mid] >= b)
                        right = mid;
                    else
                        left = mid + 1;
                }
                ret[left] = b;
            }
        }
        return ret.size();
    }
};